#include "test_avl.h"




void refresh_avl_seq_buffer()
{
    avl_tree_seq[0] = '\0';
    seq_ptr = 0;
}



void avl_preorder_seq(avl_tree r)
{
    if (NULL == r)
        return;

    seq_ptr += snprintf( avl_tree_seq + seq_ptr, AVL_SEQ_BUFFER_MAX_LEN - seq_ptr,"%d ", r->data);
    avl_preorder_seq(r->left);
    avl_preorder_seq(r->right);
}
void avl_inorder_seq(avl_tree r)
{
    if (NULL == r)
        return;
    avl_inorder_seq(r->left);
    
    seq_ptr += snprintf( avl_tree_seq + seq_ptr, AVL_SEQ_BUFFER_MAX_LEN - seq_ptr,"%d ", r->data);
    

    avl_inorder_seq(r->right);
}
void avl_postorder_seq(avl_tree r)
{
    if (NULL == r)
        return;
    avl_postorder_seq(r->left);
    avl_postorder_seq(r->right);
    seq_ptr += snprintf( avl_tree_seq + seq_ptr, AVL_SEQ_BUFFER_MAX_LEN  - seq_ptr,"%d ", r->data);
}
static int cmp(const void *a, const void *b)
{
    return *(int *) a - *(int *) b;
}
static void test_avl_insert_rand( void )
{
    avl_tree rt = NULL;


    int repeat_cnt = 0;
    char seq_str[200];
    memset(seq_str, 0, sizeof(seq_str));
    srand(time(NULL));
    int seq[10];
    printf("insert order: ");
    for (int i = 0; i < 10; ++i) {
        int v = rand() % 1000;
        printf("%d ", v);
        for (int j = 0;j < i; ++j)
            if (seq[j] == v)
                repeat_cnt++;
        seq[i] = v;    
        avl_tree_insert( &rt, v );
    }
    printf("\n");

    int p = 0;
    qsort(seq, 10, sizeof(seq[0]),cmp);
    for (int i = 0;i < 10; ++i) 
        p += sprintf(seq_str + p, "%d ", seq[i]);
    seq_str[p++]='\n';
    seq_str[p++]='\0'; 

    refresh_avl_seq_buffer();
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++]='\n';
    avl_tree_seq[seq_ptr++]='\0';
    if (repeat_cnt)
        printf("repeat_cnt: %d\n", repeat_cnt);

    printf("expected: %s", seq_str);
    printf("------------\n");
    printf("actually: %s", avl_tree_seq);
    CU_ASSERT_STRING_EQUAL(avl_tree_seq, seq_str);
    
    avl_tree_free( &rt );
}

static void test_lll_adjust(void)
{
    avl_tree rt = NULL;
    avl_tree_insert(&rt, 3);
    avl_tree_insert(&rt, 2);
    avl_tree_insert(&rt, 1);

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

   

    CU_ASSERT_STRING_EQUAL(avl_tree_seq, "2 1 3 \n1 2 3 \n");

    avl_tree_free(&rt);
}



static void test_rrr_adjust(void)
{
    avl_tree rt = NULL;
    avl_tree_insert(&rt, 3);
    avl_tree_insert(&rt, 4);
    avl_tree_insert(&rt, 5);

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL(avl_tree_seq, "4 3 5 \n3 4 5 \n");


    avl_tree_free(&rt);
}

static void test_lr_adjust(void)
{
    avl_tree rt = NULL;
    avl_tree_insert(&rt, 7);
    avl_tree_insert(&rt, 4);
    avl_tree_insert(&rt, 6);

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL(avl_tree_seq, "6 4 7 \n4 6 7 \n");

    avl_tree_free(&rt);
}

static void test_rl_adjust(void)
{
    avl_tree rt = NULL;
    avl_tree_insert(&rt, 4);
    avl_tree_insert(&rt, 8);
    avl_tree_insert(&rt, 5);
    avl_tree_insert(&rt, 9);
    avl_tree_insert(&rt, 10);

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL(avl_tree_seq, "5 4 9 8 10 \n4 5 8 9 10 \n");
    avl_tree_free(&rt);
}


static void test_avl_find(void)
{
    avl_tree rt = NULL;
    avl_tree_insert(&rt, 7);
    avl_tree_insert(&rt, 4);
    avl_tree_insert(&rt, 6);

    CU_ASSERT_TRUE(avl_tree_find(&rt, 7));
    CU_ASSERT_TRUE(avl_tree_find(&rt, 4));
    CU_ASSERT_TRUE(avl_tree_find(&rt, 6));

    CU_ASSERT_FALSE(avl_tree_find(&rt, 0));
    CU_ASSERT_FALSE(avl_tree_find(&rt, 1));
    CU_ASSERT_FALSE(avl_tree_find(&rt, 2));

    avl_tree_free(&rt);
}
static void test_avl_delete_root(void)
{
    avl_tree rt = NULL;
    avl_tree_insert( &rt, 7 );
    avl_tree_insert( &rt, 4 );
    avl_tree_insert( &rt, 6 );


    CU_ASSERT_FALSE( avl_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  avl_tree_delete( &rt, 6 ) );

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( avl_tree_seq, "4 7 \n4 7 \n");


    avl_tree_free( &rt );
}
static void test_avl_delete_leaf(void)
{
    avl_tree rt = NULL;
    avl_tree_insert( &rt, 7 );
    avl_tree_insert( &rt, 6 );
    avl_tree_insert( &rt, 8 );
    avl_tree_insert( &rt, 9 );

    CU_ASSERT_FALSE( avl_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  avl_tree_delete( &rt, 6 ) );

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( avl_tree_seq, "8 7 9 \n7 8 9 \n");


    avl_tree_free( &rt );
}

static void test_avl_delete_simple(void)
{
    avl_tree rt = NULL;
    avl_tree_insert( &rt, 7 );
    avl_tree_insert( &rt, 4 );
    avl_tree_insert( &rt, 8 );
    avl_tree_insert( &rt, 3 );
    avl_tree_insert( &rt, 5 );

    CU_ASSERT_FALSE( avl_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  avl_tree_delete( &rt, 4 ) );

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( avl_tree_seq, "7 3 5 8 \n3 5 7 8 \n");


    avl_tree_free( &rt );
}

static void test_avl_delete_only_one(void)
{
    avl_tree rt = NULL;
    avl_tree_insert( &rt, 7 );

    CU_ASSERT_FALSE( avl_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  avl_tree_delete( &rt, 7 ) );

    refresh_avl_seq_buffer();

    avl_preorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++] = '\n';
    avl_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( avl_tree_seq, "\n\n");


    avl_tree_free( &rt );
}

static void test_avl_delete_rand( void )
{
    avl_tree rt = NULL;


    char seq_str[200];
    memset(seq_str, 0, sizeof(seq_str));
    srand(time(NULL));
    int seq[10];

    int rep_cnt = 0;
    int dval;
    for (int i = 0; i < 10; ++i) {
        
        

        int v = rand();
        if (i == 9)
            dval = v;
        for (int j = 0;j < i;++j)
            if (seq[j] == v)
                rep_cnt++;

        seq[i] = v;    
        avl_tree_insert( &rt, v );
    }
    int p = 0;
    qsort(seq, 9, sizeof(seq[0]),cmp);
    for (int i = 0;i < 9; ++i) 
        p += sprintf(seq_str + p, "%d ", seq[i]);
    seq_str[p++]='\n';
    seq_str[p++]='\0'; 


    avl_tree_delete( &rt, dval);
    refresh_avl_seq_buffer();
    avl_inorder_seq(rt);
    avl_tree_seq[seq_ptr++]='\n';
    avl_tree_seq[seq_ptr++]='\0';

    if (rep_cnt)
        printf("rep_cnt: %d\n", rep_cnt);
    printf("expected: %s", seq_str);
    printf("------------\n");
    printf("actually: %s", avl_tree_seq);
    CU_ASSERT_STRING_EQUAL(avl_tree_seq, seq_str);
    
    avl_tree_free( &rt );
}

static CU_TestInfo test_avlInsert[] = {
    {"test_lll_adjust", test_lll_adjust},
    {"test_rrr_adjust", test_rrr_adjust},
    {"test_lr_adjust", test_lr_adjust},
    {"test_rl_adjust", test_rl_adjust},
    {"test_avl_insert_rand", test_avl_insert_rand},
    CU_TEST_INFO_NULL,
};
static CU_TestInfo test_avlFind[] = {
    {"test_avl_find", test_avl_find},
    CU_TEST_INFO_NULL,
};
static CU_TestInfo test_avlDelete[] = {
    {"test_avl_delete_root", test_avl_delete_root},
    {"test_avl_delete_leaf", test_avl_delete_leaf},
    {"test_avl_delete_simple", test_avl_delete_simple},
    {"test_avl_delete_only_one", test_avl_delete_only_one},
    {"test_avl_delete_rand", test_avl_delete_rand},
    CU_TEST_INFO_NULL,
};

static CU_SuiteInfo suites[] = {
    {"suite_test_insert", NULL, NULL, NULL, NULL, test_avlInsert},
    {"suite_test_find",   NULL, NULL, NULL, NULL, test_avlFind},
    {"suite_test_delete", NULL, NULL, NULL, NULL, test_avlDelete},
    CU_SUITE_INFO_NULL,
};

void AddTests(void)
{
    assert(NULL != CU_get_registry());
    assert(!CU_is_test_running());

    if (CU_register_suites(suites) != CUE_SUCCESS) {
        fprintf(stderr, "suite registration failed - %s \n", 
            CU_get_error_msg());        
        exit(EXIT_FAILURE);
    }
}